Recap: Types of Binary Trees

  • Full Binary Tree: Every node has either 0 or 2 children.
  • Perfect Binary Tree: A full binary tree where all leaf nodes are at the same level.
  • Complete Binary Tree: Every level is completely filled, except possibly the last, which is filled from left to right without gaps.

What is a Binary Heap?

A Binary Heap is a special binary tree that satisfies two properties:

  • 1. Shape Property: It must be a complete binary tree.
    • This structure ensures the tree is as compact as possible.
    • It allows the tree to be efficiently stored in an array.
  • 2. Heap Property: The value of each node must be greater than or equal to the value of its children. This is known as a Max-Heap. (For a Min-Heap, it's the reverse).
100 19 36 17 3 25 1
Tree is a Complete Binary Tree